package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript:数组中只出现一次的数字
 * 一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
 * 解题思路   https://cuijiahua.com/blog/2018/01/basis_40.html
 * 个人解法: a,b,c,d,d,a  -->用数组存，有的话，就移除
 * @date: 2021/3/18 22:24
 * @version: 1.0
 */
public class Q40_FindNumsAppearOnce {
    public static void main(String[] args) {
        int[] arr={2,6,3,4,3,2,5,5};
        //位上不同的数为1，相同的数为0 （1,0）->1,(0,1)->1,(0,0)->0,(1,1)->0
        int xorSum = 0;
        for(int num : arr){  //如果只是求一个数组中的只有一位是不一样的，那么通过加一个减一个的方式
            xorSum ^= num;
        }

        //取xorSum二进制表示中低位为1的bit位，将其它的bit位 置0
        //比如：xorSum = 1100，那么 (1100 ^ 1011) & 1100 = 0100，只剩下一个为1的bit位
        xorSum = (xorSum ^ (xorSum - 1)) & xorSum;
        int[] num1=new int[2];
        num1[0]=0;
        num1[1]=0;
        for (int num:arr) {

            //xorSum是只有一个位是1，那么任何数跟它相与，要么为0，要么不是0：
            // 现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，
            // 第一个子数组中每个数字与xorSum第n位做与运算都是1(不等于0)，
            // 而第二个子数组中每个数字的第n位都是0,就是为0。
            //分成两个组之后，就可以通过逐个异或取到孤零零的那个值了
            num1[0] = (num & xorSum) == 0 ? num1[0] ^ num : num1[0];
            num1[1] = (num & xorSum) != 0 ? num1[1] ^ num : num1[1];
        }
        System.out.println(swap(num1));
    }

    private static int[] swap(int[] num1){
        if (num1[0]>num1[1]){
            int temp=num1[0];
            num1[0]=num1[1];
            num1[1]=temp;
        }
        return num1;
    }

}
